#include "SeqString.h"
#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 1024
#define OK 1
#define ERROR 0

typedef char AtomType;               //元素类型为字符型
typedef enum { ATOM, LIST } ElemTag; /*ATOM=0，表示原子，LIST=1，表示子表*/
                                     //广义表的存储结构
typedef struct GLNode {
  ElemTag tag; //标志域
  union {
    AtomType atom; //值域
    struct {
      struct GLNode *hp, *tp;
    } ptr;
  };
} GLNode, *GList;

// typedef struct GLNode *GList, GLnode;
void CreateList(GList *L, SeqString S);
void DistributeString(SeqString *Str, SeqString *HeadStr);
void StrPrint(SeqString S);
void PrintGList2(GList L);
int SubString(SeqString *Sub, SeqString S, int pos, int len);
int GListLength(GList L);
int GListDepth(GList L);
GLNode *GetHead(GList L);
GLNode *GeTail(GList L);

/*创建广义表的函数*/
void CreateList(GList *L, SeqString S) {
  SeqString Sub, HeadSub, Empty;
  GList p, q;
  StrAssign(&Empty, "()");
  if (!StrCompare(S, Empty)) {
    *L = NULL;
  } else {
    if (!(*L = (GList)malloc(sizeof(GLNode)))) {
      exit(-1);
    }
    if (StrLength(S) == 1) {
      (*L)->tag = ATOM;
      (*L)->atom = S.str[0];
    } else {
      (*L)->tag = LIST;
      p = *L;
      SubString(&Sub, S, 2, StrLength(S) - 2);
      do {
        DistributeString(&Sub, &HeadSub);
        CreateList(&(p->ptr.hp), HeadSub);
        q = p;
        if (!StrEmpty(Sub)) {
          if (!(p = (GLNode *)malloc(sizeof(GLNode)))) {
            exit(-1);
          }
          p->tag = LIST;
          q->ptr.tp = p;
        }
      } while (!StrEmpty(Sub));

      q->ptr.tp = NULL;
    }
  }
}

/*打印广义表的函数*/
void PrintGList2(GList L) {
  GLNode *p;
  if (!L) {
    printf("()\n");
  } else {

    if (L->tag == ATOM) {
      printf("%c", L->atom);
    } else {
      p = NULL;
      printf("(");
      p = L;
      while (p) {
        PrintGList2(p->ptr.hp);
        p = p->ptr.tp;
        if (p) {
          printf(",");
        }
      }
      printf(")");
    }
  }
}
/*打印字符串函数*/
void StrPrint(SeqString S) {
  int i;
  for (i = 0; i < S.length; i++) {
    printf("%c", S.str[i]);
  }

  printf("\n");
}

/*字符串求子串函数*/
int SubString(SeqString *Sub, SeqString S, int pos, int len) {
  int i;
  if (pos < 0 || len < 0 || pos + len - 1 > S.length) {
    printf("参数pos和len不合法。");
    return 0;
  } else {
    for (i = 0; i < len; i++) {
      Sub->str[i] = S.str[i + pos - 1];
    }
    Sub->length = len;
    return 1;
  }
}

/*求广义表的表头函数*/
GLNode *GetHead(GList L) {
  //请完成本函数的功能
  if (L == NULL) {
    return NULL;
  }
  if (L->tag == ATOM) {
    exit(0);
  } else {
    return L->ptr.hp;
  }
}
/*取尾操作函数*/
GLNode *GeTail(GList L) {
  //请完成本函数的功能
  if (L == NULL) {
    return NULL;
  }
  if (L->tag == ATOM) {
    exit(0);
  } else {
    return L->ptr.tp;
  }
}

/*求广义表的长度函数*/
int GListLength(GList L) {
  //请完成本函数的功能
  int k = 0;
  GLNode *s;
  if (L == NULL) {
    return 0;
  }
  if (L->tag == ATOM) {
    exit(0);
  }
  s = L;
  while (s != NULL) {
    k++;
    s = s->ptr.tp;
  }
  return k;
}

/*求广义表的深度函数*/
int GListDepth(GList L) {
  //请完成本函数的功能
  int d, max;
  GLNode *s;
  if (L == NULL) {
    return 1;
  }
  if (L->tag == ATOM) {
    return 0;
  }
  s = L;
  while (s != NULL) {
    d = GListDepth(s->ptr.hp);
    if (d > max) {
      max = d;
    }
    s = s->ptr.tp;
  }
  return max + 1;
}

/*统计广义表中的原子数目函数*/
int CountAtom(GList L) {
  //请完成本函数的功能
  int n1, n2;
  if (L == NULL) {
    return 0;
  }
  if (L->tag == ATOM) {
    return 1;
  }
  n1 = CountAtom(L->ptr.hp);
  n2 = CountAtom(L->ptr.tp);
  return n1 + n2;
}

/*复制广义表函数*/
int CopyGList2(GList S, GList *T) {
  //请完成本函数的功能
  if (S == NULL) {
    *T = NULL;
    return 0;
  }
  *T = (GLNode *)malloc(sizeof(GLNode));
  if(*T==NULL){
    return ERROR;
  }
  (*T)->tag = S->tag;
  if(S->tag == ATOM){
    (*T)->atom=S->atom;
  }
  else {
    CopyGList2(S->ptr.hp,&((*T)->ptr.hp));
    CopyGList2(S->ptr.tp,&((*T)->ptr.tp));
  }
  return OK;
}

void DistributeString(SeqString *Str, SeqString *HeadStr) {
  int len, i, k;
  SeqString Ch, Ch1, Ch2, Ch3;
  len = StrLength(*Str);
  StrAssign(&Ch1, ",");
  StrAssign(&Ch2, "(");
  StrAssign(&Ch3, ")");
  SubString(&Ch, *Str, 1, 1);
  for (i = 1, k = 0; i <= len && StrCompare(Ch, Ch1) || k != 0; i++) {
    SubString(&Ch, *Str, i, 1);
    if (!StrCompare(Ch, Ch2)) {
      k++;
    } else if (!StrCompare(Ch, Ch3)) {
      k--;
    }
  }

  if (i <= len) {
    SubString(HeadStr, *Str, 1, i - 2);
    SubString(Str, *Str, i, len - i + 1);
  } else {
    StrCopy(HeadStr, *Str);
    StrClear(Str);
  }
}

int main(void) {
  GList L;
  SeqString S;
  char *str1;
  str1 = (char *)malloc(sizeof(char) * MAXSIZE);
  int depth, length;
  int flag = 1;
  int choice;
  int num;
  GList T;
  int m = 0;
  while (flag) {
    printf("请输入要进行的操作序号\n");
    printf("1.创建广义表\n");
    printf("2.求广义表的表头\n");
    printf("3.求广义表的表尾\n");
    printf("4.求广义表的长度\n");
    printf("5.求广义表的深度\n");
    printf("6.统计广义表中原子数目\n");
    printf("7.复制广义表\n");
    scanf("%d", &choice);
    switch (choice) {
    case 1:
      printf("请输入广义表：\n");
      scanf("%s", str1);
      // StrAssign(&S, "(a,b,c,(a,(a,b,(a,b,c,d),e,f)))");
      StrAssign(&S, str1);
      CreateList(&L, S);
      printf("广义表为：\n");
      PrintGList2(L);
      printf("\n");
      break;
    case 2:
      GetHead(L);
      break;
    case 3:
      GeTail(L);
      break;
    case 4:
      length = GListLength(L);
      printf("广义表的长度是：%d\n", length);
      break;
    case 5:
      depth = GListDepth(L);
      printf("广义表的深度是：%d\n", depth);
      break;
    case 6:
      num = CountAtom(L);
      printf("该广义表中的原子数目是：%d\n", num);
      break;
    case 7:
      m = CopyGList2(L, &T);
      if (m == 1) {
        printf("复制的广义表成功!\n");
      } else
        printf("复制的广义表失败!\n");
      break;
    default:
      printf("输入错误，请重新输入\n");
    }
  }
  return 0;
}
